#include <graphics/Terrain.h>

namespace ne
{
    Terrain::Terrain(const std::string &name)
        : Object(name),
          mpTriangle(0),
          mWidth(0),
          mHeight(0),
          mpHeightData(0),
          mCameraPos(Vector3::ZERO)
    {
    }

    void Terrain::generateTerrainData(Image *pHeightData)
    {
        if (pHeightData)
        {
            destroyTerrainData();

            mpHeightData = pHeightData;
            mWidth = mpHeightData->getWidth();
            mHeight = mpHeightData->getHeight();

            // Generate vertex data
            for (uint32_t y=0; y<mHeight; ++y)
            {
                for (uint32_t x=0; x<mWidth; ++x)
                {
                    Color c = mpHeightData->getColorAt(x, y);
                    mVertexList.push_back(Vector4(4.0f * x, _getHeightFromColor(c), 4.0f * y, c.a));
                }
                Color c = mpHeightData->getColorAt(mWidth - 1, y);
                mVertexList.push_back(Vector4(4.0f * mWidth, _getHeightFromColor(c), 4.0f * y, c.a));
            }
            for (uint32_t x=0; x<mWidth; ++x)
            {
                Color c = mpHeightData->getColorAt(x, mHeight - 1);
                mVertexList.push_back(Vector4(4.0f * x, _getHeightFromColor(c), 4.0f * mHeight, c.a));
            }
            Color c = mpHeightData->getColorAt(mWidth - 1, mHeight - 1);
            mVertexList.push_back(Vector4(4.0f * mWidth, _getHeightFromColor(c), 4.0f * mHeight, c.a));

            // Generate normal data
            for (uint32_t y=0; y<=mHeight; ++y)
            {
                for (uint32_t x=0; x<=mWidth; ++x)
                {
                    _generateNormalAndColorAt(x, y);
                }
            }

            // Create root triangle
            mpTriangle = new TerrainTriangle();
            TerrainTriangle *pBottomNeighbor = new TerrainTriangle();

            mpTriangle->mFace[0] = 0;
            mpTriangle->mFace[1] = (mWidth + 1) * mHeight;
            mpTriangle->mFace[2] = (mWidth + 1) * (mHeight + 1) - 1;
            mpTriangle->mMinHeight = FLT_MAX;
            mpTriangle->mMaxHeight = -FLT_MAX;
            mpTriangle->mpParent = 0;
            mpTriangle->mpLeftChild = 0;
            mpTriangle->mpRightChild = 0;
            mpTriangle->mpLeftNeighbor = 0;
            mpTriangle->mpRightNeighbor = 0;
            mpTriangle->mpBottomNeighbor = pBottomNeighbor;
            mpTriangle->mSplit = false;

            pBottomNeighbor->mFace[0] = (mWidth + 1) * (mHeight + 1) - 1;
            pBottomNeighbor->mFace[1] = mWidth;
            pBottomNeighbor->mFace[2] = 0;
            pBottomNeighbor->mMinHeight = FLT_MAX;
            pBottomNeighbor->mMaxHeight = -FLT_MAX;
            pBottomNeighbor->mpParent = 0;
            pBottomNeighbor->mpLeftChild = 0;
            pBottomNeighbor->mpRightChild = 0;
            pBottomNeighbor->mpLeftNeighbor = 0;
            pBottomNeighbor->mpRightNeighbor = 0;
            pBottomNeighbor->mpBottomNeighbor = mpTriangle;
            pBottomNeighbor->mSplit = false;

            // Split terrain
            mSplitTriangleDeque.push_back(mpTriangle);
            while (!mSplitTriangleDeque.empty())
            {
                TerrainTriangle *pTriangle = mSplitTriangleDeque.front();
                mSplitTriangleDeque.pop_front();
                _splitTerrain(pTriangle);
            }
        }
    }

    void Terrain::update(const Viewport *pViewport)
    {
        Vector3 pos = pViewport->getCamera()->getPosition();
        if (mCameraPos.distance(pos) > 64.0f)
        {
            mCameraPos = pos;

            // Update terrain
            mIndexList.clear();
            mSplitTriangleDeque.clear();
            mSplitTriangleDeque.push_back(mpTriangle);

            mUpdateTriangleMap.clear();
            mUpdateTriangleMap[mpTriangle] = false;
            mUpdateTriangleMap[mpTriangle->mpBottomNeighbor] = false;
            while (!mSplitTriangleDeque.empty())
            {
                TerrainTriangle *pTriangle = mSplitTriangleDeque.front();
                mSplitTriangleDeque.pop_front();
                _updateTerrain(pTriangle);
            }

            std::map<TerrainTriangle*, bool>::iterator it, iend;
            iend = mUpdateTriangleMap.end();
            for (it=mUpdateTriangleMap.begin(); it!=iend; ++it)
            {
                TerrainTriangle *pTriangle = it->first;
                if (!it->second)
                {
                    mIndexList.push_back(pTriangle->mFace[0]);
                    mIndexList.push_back(pTriangle->mFace[1]);
                    mIndexList.push_back(pTriangle->mFace[2]);
                }
            }
        }
    }

    const std::vector<Vector4>& Terrain::getVertexList() const
    {
        return mVertexList;
    }

    const std::vector<Vector3>& Terrain::getNormalList() const
    {
        return mNormalList;
    }

    const std::vector<Color>& Terrain::getColorList() const
    {
        return mColorList;
    }

    const std::vector<uint32_t>& Terrain::getIndexList() const
    {
        return mIndexList;
    }

    real Terrain::getHeightAt(const Vector2 &v) const
    {
        return getHeightAt(v.x, v.y);
    }

    real Terrain::getHeightAt(const Vector3 &v) const
    {
        return getHeightAt(v.x, v.z);
    }

    real Terrain::getHeightAt(const real x, const real y) const
    {
        if (x >= 0 && x <= 4.0f * mWidth &&
            y >= 0 && y <= 4.0f * mHeight)
        {
            TerrainTriangle *pTriangle = mpTriangle;
            if (x > y)
            {
                pTriangle = mpTriangle->mpBottomNeighbor;
            }

            while (pTriangle && pTriangle->mSplit)
            {
                Vector3 v0(mVertexList[pTriangle->mFace[0]].ptr());
                Vector3 v2(mVertexList[pTriangle->mFace[2]].ptr());
                real dLeft = (x - v2.x) * (x - v2.x) + (y - v2.z) * (y - v2.z);
                real dRight = (x - v0.x) * (x - v0.x) + (y - v0.z) * (y - v0.z);
                if (dLeft < dRight)
                {
                    pTriangle = pTriangle->mpLeftChild;
                }
                else
                {
                    pTriangle = pTriangle->mpRightChild;
                }
            }

            if (pTriangle && !pTriangle->mSplit)
            {
                Vector3 v0(mVertexList[pTriangle->mFace[0]].ptr());
                Vector3 v1(mVertexList[pTriangle->mFace[1]].ptr());
                Vector3 v2(mVertexList[pTriangle->mFace[2]].ptr());
                real p = 0.25f * std::abs(x - v1.x);
                real q = 0.25f * std::abs(y - v1.z);
                real h0 = 0.0f;
                real h2 = 0.0f;
                if (v0.x == v1.x)
                {
                    h0 = q * (v0.y - v1.y);
                    h2 = p * (v2.y - v1.y);
                }
                else
                {
                    h0 = p * (v0.y - v1.y);
                    h2 = q * (v2.y - v1.y);
                }
                return h0 + h2 + v1.y;
            }
        }
        return 0.0f;
    }

    void Terrain::destroyTerrainData()
    {
        if (mpTriangle)
        {
            _destroyTriangle(mpTriangle->mpBottomNeighbor);
            _destroyTriangle(mpTriangle);
            mpTriangle = 0;
            mWidth = 0;
            mHeight = 0;
            mpHeightData = 0;
            mVertexList.clear();
            mNormalList.clear();
            mColorList.clear();
            mIndexList.clear();
            mSplitTriangleDeque.clear();
            mUpdateTriangleMap.clear();
        }
    }

    Terrain::~Terrain()
    {
        destroyTerrainData();
    }

    real Terrain::_getHeightFromColor(const Color &c) const
    {
        /*
        uint32_t r = uint32_t(255.0f * c.r);
        uint32_t g = uint32_t(255.0f * c.g);
        uint32_t b = uint32_t(255.0f * c.b);
        uint32_t a = uint32_t(255.0f * c.a);
        real h = real(uint32_t((r << 24) + (g << 16) + (b << 8) + a));
        return h / real(1 << 24) - 128.0f;
        */
        return 512.0f * std::sqrt(c.r * c.r + c.g * c.g + c.b * c.b) / std::sqrt(3.0f) - 256.0f;
    }

    void Terrain::_generateNormalAndColorAt(const uint32_t x, const uint32_t y)
    {
        Vector3 normal(Vector3::UNIT_Y);
        Color color(Color::ZERO);

        if (x < mWidth && y < mHeight)
        {
            Vector3 vNow(mVertexList[(mHeight + 1) * y + x].ptr());
            Vector3 nLeft(Vector3::UNIT_Y);
            Vector3 nRight(Vector3::UNIT_Y);
            Vector3 nUp(Vector3::UNIT_Y);
            Vector3 nDown(Vector3::UNIT_Y);

            if (x != 0)
            {
                Vector4 v = mVertexList[(mHeight + 1) * y + x - 1];
                Vector3 vLeft(v.ptr());
                nLeft = (vLeft - vNow).crossProduct(Vector3::UNIT_Z);
                nLeft.normalize();
                color.r = v.w;
            }
            if (x != mWidth)
            {
                Vector4 v = mVertexList[(mHeight + 1) * y + x + 1];
                Vector3 vRight(v.ptr());
                nRight = (vRight - vNow).crossProduct(Vector3::NEGATIVE_UNIT_Z);
                nRight.normalize();
                color.g = v.w;
            }

            if (y != 0)
            {
                Vector4 v = mVertexList[(mHeight + 1) * (y - 1) + x];
                Vector3 vUp(v.ptr());
                nUp = (vUp - vNow).crossProduct(Vector3::NEGATIVE_UNIT_X);
                nUp.normalize();
                color.b = v.w;
            }
            if (y != mHeight)
            {
                Vector4 v = mVertexList[(mHeight + 1) * (y + 1) + x];
                Vector3 vDown(v.ptr());
                nDown = (vDown - vNow).crossProduct(Vector3::UNIT_X);
                nDown.normalize();
                color.a = v.w;
            }
            normal = nLeft + nRight + nUp + nDown;
            normal.normalize();
        }
        mNormalList.push_back(normal);
        mColorList.push_back(color);
    }

    bool Terrain::_needSplitTriangle(TerrainTriangle *pTriangle) const
    {
        if (pTriangle && pTriangle->mSplit)
        {
            Vector3 v0(mVertexList[pTriangle->mFace[0]].ptr());
            Vector3 v1(mVertexList[pTriangle->mFace[1]].ptr());
            Vector3 v2(mVertexList[pTriangle->mFace[2]].ptr());
            real line = std::max(std::abs(v0.x - v1.x), std::abs(v0.z - v1.z));
            real dH = pTriangle->mMaxHeight - pTriangle->mMinHeight;
            Vector3 mid = 0.5f * (v0 + v2);
            mid.y = 0.5f * (mid.y + 0.5f * (pTriangle->mMaxHeight - pTriangle->mMinHeight));
            real dis = mCameraPos.distance(mid);

            if (dis < 32.0f * line)
            {
                return true;
            }

            if (dis < 4.0f * dH)
            {
                return true;
            }
        }
        return false;
    }

    void Terrain::_splitTerrain(TerrainTriangle *pTriangle)
    {
        if (pTriangle && !pTriangle->mSplit)
        {
            if (pTriangle->mpBottomNeighbor)
            {
                if (pTriangle->mpBottomNeighbor->mpBottomNeighbor != pTriangle)
                {
                    _splitTerrain(pTriangle->mpBottomNeighbor);
                }
                _splitTriangle(pTriangle);
                _splitTriangle(pTriangle->mpBottomNeighbor);
                if (pTriangle->mSplit)
                {
                    pTriangle->mpLeftChild->mpRightNeighbor = pTriangle->mpBottomNeighbor->mpRightChild;
                    pTriangle->mpRightChild->mpLeftNeighbor = pTriangle->mpBottomNeighbor->mpLeftChild;
                }
                if (pTriangle->mpBottomNeighbor->mSplit)
                {
                    pTriangle->mpBottomNeighbor->mpLeftChild->mpRightNeighbor = pTriangle->mpRightChild;
                    pTriangle->mpBottomNeighbor->mpRightChild->mpLeftNeighbor = pTriangle->mpLeftChild;
                }
            }
            else
            {
                _splitTriangle(pTriangle);
                if (pTriangle->mSplit)
                {
                    pTriangle->mpLeftChild->mpRightNeighbor = 0;
                    pTriangle->mpRightChild->mpLeftNeighbor = 0;
                }
            }

            if (pTriangle->mSplit)
            {
                pTriangle->mMinHeight = std::min(pTriangle->mpLeftChild->mMinHeight, pTriangle->mpRightChild->mMinHeight);
                pTriangle->mMaxHeight = std::max(pTriangle->mpLeftChild->mMaxHeight, pTriangle->mpRightChild->mMaxHeight);
            }
        }
    }

    void Terrain::_splitTriangle(TerrainTriangle *pTriangle)
    {
        if (pTriangle && !pTriangle->mSplit)
        {
            Vector3 v0(mVertexList[pTriangle->mFace[0]].ptr());
            Vector3 v1(mVertexList[pTriangle->mFace[1]].ptr());
            Vector3 v2(mVertexList[pTriangle->mFace[2]].ptr());

            if (std::abs(v0.x - v1.x) + std::abs(v0.z - v1.z) > 4.0f)
            {
                pTriangle->mSplit = true;

                uint32_t x = uint32_t(0.125f * (v0.x + v2.x) + 0.5f);
                uint32_t y = uint32_t(0.125f * (v0.z + v2.z) + 0.5f);
                uint32_t index = (mWidth + 1) * y + x;

                // Create left child
                pTriangle->mpLeftChild = new TerrainTriangle();
                TerrainTriangle *pLeftChild = pTriangle->mpLeftChild;
                pLeftChild->mFace[0] = pTriangle->mFace[2];
                pLeftChild->mFace[1] = index;
                pLeftChild->mFace[2] = pTriangle->mFace[1];
                pLeftChild->mMinHeight = FLT_MAX;
                pLeftChild->mMaxHeight = -FLT_MAX;
                pLeftChild->mpParent = pTriangle;
                pLeftChild->mpLeftChild = 0;
                pLeftChild->mpRightChild = 0;
                pLeftChild->mSplit = false;
                for (uint32_t i=0; i<3; ++i)
                {
                    real h = mVertexList[pLeftChild->mFace[i]].y;
                    pLeftChild->mMinHeight = std::min(pLeftChild->mMinHeight, h);
                    pLeftChild->mMaxHeight = std::max(pLeftChild->mMaxHeight, h);
                }

                // Create right child
                pTriangle->mpRightChild = new TerrainTriangle();
                TerrainTriangle *pRightChild = pTriangle->mpRightChild;
                pRightChild->mFace[0] = pTriangle->mFace[1];
                pRightChild->mFace[1] = index;
                pRightChild->mFace[2] = pTriangle->mFace[0];
                pRightChild->mMinHeight = FLT_MAX;
                pRightChild->mMaxHeight = -FLT_MAX;
                pRightChild->mpParent = pTriangle;
                pRightChild->mpLeftChild = 0;
                pRightChild->mpRightChild = 0;
                pRightChild->mSplit = false;
                for (uint32_t i=0; i<3; ++i)
                {
                    real h = mVertexList[pRightChild->mFace[i]].y;
                    pRightChild->mMinHeight = std::min(pRightChild->mMinHeight, h);
                    pRightChild->mMaxHeight = std::max(pRightChild->mMaxHeight, h);
                }

                pLeftChild->mpLeftNeighbor = pRightChild;
                pRightChild->mpRightNeighbor = pLeftChild;

                pLeftChild->mpBottomNeighbor = pTriangle->mpLeftNeighbor;
                if (pTriangle->mpLeftNeighbor)
                {
                    if (pTriangle->mpLeftNeighbor->mpBottomNeighbor == pTriangle)
                    {
                        pTriangle->mpLeftNeighbor->mpBottomNeighbor = pLeftChild;
                    }
                    else
                    {
                        pTriangle->mpLeftNeighbor->mpRightNeighbor = pLeftChild;
                    }
                }

                pRightChild->mpBottomNeighbor = pTriangle->mpRightNeighbor;
                if (pTriangle->mpRightNeighbor)
                {
                    if (pTriangle->mpRightNeighbor->mpBottomNeighbor == pTriangle)
                    {
                        pTriangle->mpRightNeighbor->mpBottomNeighbor = pRightChild;
                    }
                    else
                    {
                        pTriangle->mpRightNeighbor->mpLeftNeighbor = pRightChild;
                    }
                }

                mSplitTriangleDeque.push_back(pLeftChild);
                mSplitTriangleDeque.push_back(pRightChild);
            }
        }
    }

    void Terrain::_updateTerrain(TerrainTriangle *pTriangle, const bool bForce)
    {
        if (pTriangle)
        {
            if (pTriangle->mSplit && !mUpdateTriangleMap[pTriangle])
            {
                bool bNeedUpdate = true;
                if (!bForce)
                {
                    bNeedUpdate = _needSplitTriangle(pTriangle);
                }
                if (bNeedUpdate)
                {
                    _updateTriangle(pTriangle);
                    if (pTriangle->mpBottomNeighbor)
                    {
                        if (pTriangle->mpBottomNeighbor->mpBottomNeighbor != pTriangle)
                        {
                            _updateTerrain(pTriangle->mpBottomNeighbor, true);
                        }
                        _updateTriangle(pTriangle->mpBottomNeighbor);
                    }
                }
            }
            _updateTerrain(pTriangle->mpParent, true);
        }
    }

    void Terrain::_updateTriangle(TerrainTriangle *pTriangle)
    {
        if (pTriangle && pTriangle->mSplit && !mUpdateTriangleMap[pTriangle])
        {
            mUpdateTriangleMap[pTriangle] = true;

            std::map<TerrainTriangle*, bool>::iterator it = mUpdateTriangleMap.find(pTriangle->mpLeftChild);
            if (it == mUpdateTriangleMap.end())
            {
                mUpdateTriangleMap[pTriangle->mpLeftChild] = false;
                mSplitTriangleDeque.push_back(pTriangle->mpLeftChild);
            }

            it = mUpdateTriangleMap.find(pTriangle->mpRightChild);
            if (it == mUpdateTriangleMap.end())
            {
                mUpdateTriangleMap[pTriangle->mpRightChild] = false;
                mSplitTriangleDeque.push_back(pTriangle->mpRightChild);
            }
        }
    }

    void Terrain::_destroyTriangle(TerrainTriangle *pTriangle)
    {
        if (pTriangle)
        {
            if (pTriangle->mSplit)
            {
                _destroyTriangle(pTriangle->mpLeftChild);
                _destroyTriangle(pTriangle->mpRightChild);
            }
            delete pTriangle;
        }
    }
}
